package cengxubianli

import "hufeng/ercahshu"

func levelOrderBottom(root *ercahshu.TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	ans := make([][]int, 0)
	queue := make([]*ercahshu.TreeNode, 0)
	queue = append(queue, root)
	for len(queue) > 0 {
		n := len(queue)
		cur := make([]int, 0)
		for _, v := range queue {
			if v != nil {
				cur = append(cur, v.Val)
				if v.Left != nil {
					queue = append(queue, v.Left)
				}
				if v.Right != nil {
					queue = append(queue, v.Right)
				}
			}
		}
		queue = queue[n:]
		ans = append(ans, cur)
	}
	left, right := 0, len(ans)-1
	for left < right {
		ans[left], ans[right] = ans[right], ans[left]
		left++
		right--
	}
	return ans
}
